package com.zang.backtrack;

import java.util.*;

/**
 * @author ZVerify
 * @since 2022/11/13 16:38
 * @see <a href="https://leetcode.cn/problems/restore-ip-addresses/description/">...</a>
 **/
public class 复原IP地址 {

    // 保存结果
    List<String> result = new ArrayList<>();
    // 保存中间结果
    LinkedList<String> list = new LinkedList<>();

    public List<String> restoreIpAddresses(String s) {
        // 不符合规范直接返回null
        if (s.length()>12) return Collections.emptyList();

        backtrack(s,0);
        return result;
    }

    private void backtrack(String s, int startIndex) {
        // 当到达结尾的时候恰好是四个数则正确
        if (startIndex == s.length() && list.size()==4) {
            result.add(toResult(list));
            return;
        }

        for (int i = startIndex; i< s.length(); i++) {

            String str = s.substring(startIndex,i+1);
            // 如果当前要判断的不符合直接修剪掉
            if(!isValid(str)) continue;
            // 添加
            list.addLast(str);
            // 递归
            backtrack(s, i+1);
            // 回溯
            list.pollLast();
        }

    }

    public String toResult(Deque<String> path){
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < path.size(); i++){
            sb.append(list.get(i));
            if(i != path.size() - 1)
                sb.append(".");
        }
        return sb.toString();
    }
    public boolean isValid(String s){
        if(s.length()==1) return true;
        if(s.length()>3) return false;
        if(s.charAt(0) == '0') return false;
        if(Integer.parseInt(s) > 255) return false;
        return true;
    }
}
